#include "list.hpp"

#include <cassert>
#include <algorithm>
#include <utility>

namespace vl
{

namespace
{

typedef std::pair<list_node_common*, list_node_common*> range;

}

list_node_common* list_common::push_back(list_node_common* el)
{
	sentinel_.prev_->next_ = el;
	el->prev_ = sentinel_.prev_;
	el->next_ = &sentinel_;
	sentinel_.prev_ = el;

	return el;
}

size_t list_common::size()
{
	list_node_common* n = first();
	size_t c = 0;
	for(; n != &sentinel_; n = n->next_)
		++c;
	return c;
}

list_node_common* list_common::unlink(list_node_common* i)
{
	list_node_common* n = i->next_;
	
	i->unlink();

	return n;
}

list_node_common* list_common::insert(list_node_common* b, list_node_common* el)
{
	el->next_ = b;
	el->prev_ = b->prev_;
	b->prev_->next_ = el;
	b->prev_ = el;

	return el;
}

list_node_common* list_common::insert_after(list_node_common* b, list_node_common* el)
{
	el->next_ = b->next_;
	el->prev_ = b;
	b->next_->prev_ = el;
	b->next_ = el;

	return el;
}

void list_common::swap(list_common& b)
{
	std::swap(sentinel_.next_, b.sentinel_.next_);
	std::swap(sentinel_.prev_, b.sentinel_.prev_);
}

range list_sort_private(
	list_node_common* section,
	void* comparer,
	do_list_compare_func do_compare)
{
	list_node_common* pivot = section;
	
	if(pivot->next_ == 0)
		return std::make_pair(pivot, pivot); // Section is sorted (only one element)
		
	/*
	list_node_common* lo = 0;
	list_node_common* hi = 0;
	*/
	list_node_common lo, hi;
		
	lo.prev_ = &lo;
	lo.next_ = &lo;
	
	hi.prev_ = &hi;
	hi.next_ = &hi;
	
	list_node_common* i = pivot->next_;
	while(i)
	{
		list_node_common* next = i->next_;
		
		//if(op(*static_cast<T*>(i), *static_cast<T*>(pivot)))
		if(do_compare(comparer, i, pivot))
		{
			lo.prev_->next_ = i;
			i->next_ = &lo;
			lo.prev_ = i;
		}
		else
		{
			hi.prev_->next_ = i;
			i->next_ = &hi;
			hi.prev_ = i;
		}
		
		i = next;
	}
	
	range ret;
	
	if(lo.next_ != &lo)
	{
		lo.prev_->next_ = 0;
		range p = list_sort_private(lo.next_, comparer, do_compare);
		p.second->next_ = pivot;
		ret.first = p.first;
	}
	else
		ret.first = pivot;
	
	if(hi.next_ != &hi)
	{
		hi.prev_->next_ = 0;
		range p = list_sort_private(hi.next_, comparer, do_compare);
		pivot->next_ = p.first;
		ret.second = p.second;
	}	
	else
		ret.second = pivot;
				
	return ret;
}

void list_common::sort(void* comparer, do_list_compare_func do_compare)
{
	if(sentinel_.next_ == &sentinel_) // empty
		return;
		
	list_node_common* f = first();
	
	last()->next_ = 0; // Break the chain
	
	range p(list_sort_private(f, comparer, do_compare));
	
	p.second->next_ = 0; // Sorting might have left a connection at the end

	sentinel_.next_ = p.first;	
	sentinel_.prev_ = p.second;
		
	// Correct the prev pointers
	list_node_common* i = sentinel_.next_;
	list_node_common* l = &sentinel_;
	
	for(; i; i = i->next_) // last()->next_ is still 0, so we can do a simpler test
	{
		i->prev_ = l;
		l = i;
	}
	
	last()->next_ = &sentinel_; // Connect the chain again
	
}

}
